Semidefinite Relaxation for Two Mixed Binary Quadratically Constrained Quadratic Programs: Algorithms and Approximation Bounds

摘要

This paper develops new semidefinite programming (SDP) relaxation techniquesfor two classes of mixed binary quadratically constrained quadratic programs(MBQCQP) and analyzes their approximation performance. The first class ofproblem finds two minimum norm vectors in $N$-dimensional real or complexEuclidean space, such that $M$ out of $2M$ concave quadratic functions aresatisfied. By employing a special randomized rounding procedure, we show thatthe ratio between the norm of the optimal solution of this model and its SDPrelaxation is upper bounded by $\frac{54M^2}{\pi}$ in the real case and by$\frac{24M}{\sqrt{\pi}}$ in the complex case. The second class of problem findsa series of minimum norm vectors subject to a set of quadratic constraints anda cardinality constraint with both binary and continuous variables. We showthat in this case the approximation ratio is also bounded and independent ofproblem dimension for both the real and the complex cases.